package junior.回溯法;
import java.util.*;

public class 回溯算法框架_子集_无重复元素 {
    static int[] stack = new int[10000]; // 标志位
    static int top = 0;
    static List<List<Integer>> listList = new ArrayList<>();
    static int[] nums1 = {1,2,3};
    static int[] nums2 = {4,4,1,4};
    public static void main(String[] args) {

        System.out.println("无重复元素子集:");
        fun1(nums1,0);
        System.out.println("********************");
        System.out.println("有重复元素子集:");
        subsets(nums2);
    }

    /**
     * 无重复元素 的子集
     * @param nums1
     * @param n
     */
    public static void fun1(int[] nums1,int n){
        if(n == nums1.length){  // n 个元素里面选 r个元素
            int flag = 0; // 标记子集不为空集
            for (int i = 0; i < top; i++) {
                if(stack[i] != 0){
                    System.out.print(nums1[i]+"\t");
                    flag = 1;
                }
            }
            if(flag == 0)
                System.out.print("空集");
            System.out.println();
            return;
        }
        for (int i = 0; i <= 1; i++) {  //两个状态位，允许重复组合
            stack[top++] = i;
            fun1(nums1,n+1);
            top--;
        }
    }

    /**
     * 有重复元素 的子集
     * @param nums2
     */
    public static List<List<Integer>> subsets(int[] nums2) {
        // 排序，去掉组合组合子集
        for (int i = 0; i < nums2.length-1; i++) {
            for (int j = 0; j < nums2.length-1-i; j++) {
                if(nums2[j] > nums2[j+1]){
                    int temp = nums2[j+1];
                    nums2[j+1] = nums2[j];
                    nums2[j] = temp;
                }
            }
        }
        // 初始化
        for (int i = 0; i < 100; i++) {
            stack[i] = 0;
        }
        top = 0;
        listList.clear();
        // 递归计算
        fun2(nums2, 0);
        System.out.println("无去重子集");
        System.out.println(listList);
        // 去重
        int[] check = new int[listList.size()];
        for (int i = 0; i < check.length; i++) {
            check[i] = 0;
        }
        for (int i = 0; i < listList.size(); i++) {
            for (int j = i+1; j < listList.size(); j++) {
                if(listList.get(i).equals(listList.get(j)) && check[j] == 0 && check[i] == 0){
                    check[j] = 1;
                }
            }
        }
        for (int i = check.length-1; i >=0; i--) { // List移除元素后，下标后移，故从后往前移除，不会改变下标
            if(check[i] == 1){
                listList.remove(i);
            }
        }
        System.out.println("去重子集");
        System.out.println(listList);
        return listList;
    }
    // 递归求出全部的解空间（方法同fun1）
    public static void fun2(int[] nums2,int n){
        if(n == nums2.length){  // n 个元素里面选 r个元素
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < top; i++) {
                if(stack[i] != 0){
                    list.add(nums2[i]);
                }
            }
            listList.add(list);
            return;
        }
        for (int i = 0; i <= 1; i++) {  //两个状态位，允许重复组合
            stack[top++] = i;
            fun2(nums2,n+1);
            top--;
        }
    }
}
